package leetcode.year2021.month11;

// 494. 目标和    todo 待使用动态规划解决，（背包问题）
public class _12_3FindTargetSumWays494 {
  int ans = 0;
  public int findTargetSumWays(int[] nums, int target) {
    // 使用回溯，在长度达到length的时候，求值
    int n = nums.length;
    toFlashBack(nums, 0,0,n,target);
    return ans;
  }

  private void toFlashBack(int[] nums, int index, int sum, int length, int target) {
    if (index == length){
      if (sum == target){
        ans++;
      }
      return;
    }
    toFlashBack(nums,index + 1, sum - nums[index],length,target);
    toFlashBack(nums,index + 1, sum + nums[index],length,target);
  }
  /**
   * 494. 目标和
   * 给你一个整数数组 nums 和一个整数 target 。
   *
   * 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
   *
   * 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
   * 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
   *
   *
   *
   * 示例 1：
   *
   * 输入：nums = [1,1,1,1,1], target = 3
   * 输出：5
   * 解释：一共有 5 种方法让最终目标和为 3 。
   * -1 + 1 + 1 + 1 + 1 = 3
   * +1 - 1 + 1 + 1 + 1 = 3
   * +1 + 1 - 1 + 1 + 1 = 3
   * +1 + 1 + 1 - 1 + 1 = 3
   * +1 + 1 + 1 + 1 - 1 = 3
   * 示例 2：
   *
   * 输入：nums = [1], target = 1
   * 输出：1
   *
   *
   * 提示：
   *
   * 1 <= nums.length <= 20
   * 0 <= nums[i] <= 1000
   * 0 <= sum(nums[i]) <= 1000
   * -1000 <= target <= 1000
   */
}
